雜湊表：原理、碰撞處理與應用

📝 歷屆考古題

• 114年 高考申論題 第三題
  請說明在使用雜湊表時，若使用鏈結串列（chaining）處理碰撞（collision）問題，則搜尋的平均時間複雜度為下列何者？O(1)、O(log n)、O(n)或 O(sqrt{n})。
  查看 AI 詳解 →
• 109年 高考申論題 第一題
  請利用 KMP（Knuth, Morris, Pratt）演算法寫出失敗函數（failure function)之定義。（4分）
  查看 AI 詳解 →
• 109年 高考申論題 第二題
  找出 pattern “abcdabcabcdabcdabc”之失敗函數（failure function）值（請填入表2 failure value 中）。（14分）
  查看 AI 詳解 →
• 109年 高考申論題 第三題
  請利用 Double Hashing 將下列 key 值放入 hash table of size 13中（如表1）：（14分） {24, 53, 17, 46, 14, 32, 37, 92} h1…
  查看 AI 詳解 →
• 109年 高考申論題 第三題
  假設(二)之 pattern 嘗試在 string “abcdabcabcdabcabcda…..”找出 pattern。當 pattern 從 index 0開始比對到 index 13都一樣，而在…
  查看 AI 詳解 →
• 108年 高考申論題 第一題
  間隔為 1（offset of 1）
  查看 AI 詳解 →
• 108年 高考申論題 第二題
  間隔為商（quotient-offset）
  查看 AI 詳解 →
• 106年 高考申論題 第一題
  雜湊函式 F(x) = x mod 13，碰撞時，採取「線性探測法」（open addressing with linear probing）來放入資料。請顯示最後的雜湊表。（5 分）
  查看 AI 詳解 →
• 106年 高考申論題 第二題
  雜湊函式 F(x) = x mod 13，碰撞時，採取「二次方探測法」（open addressing with quadratic probing）來放入資料。請顯示最後的雜湊表。（5 分）
  查看 AI 詳解 →
• 106年 高考申論題 第三題
  雜湊函式 F1(x) = x mod 13，碰撞時，採取「雙探測法」（open addressing with double hashing）來放入資料，第二雜湊函式為 F2(x) = 7－(x mo…
  查看 AI 詳解 →
• 106年 高考申論題 第四題
  若雜湊表夠大（例如 slots = 2 或更大）但資料量多時，針對三種碰撞時所採取的處理方式，請說明那一種方式較能有效率的儲存或搜尋資料？請說明那一種處理方式效率最差？（5 分）
  查看 AI 詳解 →